#求一个数的比自己小的所有互质数的算法
#队列关系:a d N,a = (a d N) % N,由a和N求d
#类似环形队列:初始点a不影响计算,实则由N求d
N = 840#求一个数的所有因数
def get_factor(a):
l = []
for i in range(1,a 1): #输出1~(a-1)
if (a % i) == 0:
l.append(i)
return l#判断2个数是否互质:公约(因)数只有1的两个数叫做互质数。
def is_coprime(a,b):
a1 = get_factor(a)
a1.remove(1)
a2 = get_factor(b)
a2.remove(1)
for i in a1:
for j in a2:
if j == i:
return 0
return 1# x * D (x 属于1~N)除不尽 N
l1 = []
for d in range(1,N):
for i in range(1,N):
if ((i * d) % N) != 0: #在N-1次循环中除不够即为所需
if i == (N - 1):
l1.append(d) #全满足
continue #继续执行下一轮判断
else:
break; #不到N就除尽不满足
print(l1)l2 = []
for i in range(1,N):
if is_coprime(i,N) == 1:
l2.append(i)
print(l2)
评论